## $Id: expression.pir 22187 2007-10-17 22:29:42Z pmichaud $

=head1 TITLE

compiler.pir - PCT::HLLCompiler subclass for the FUN language

=head2 DESCRIPTION

This file contains the FUN::HLLCompiler subclass for the FUN language.
As well the normal compiler stages it also has a tailcall stage for
after the past stage that performs tailcall optimization on the code
being compiled.

Tailcall optimization is a special way of transfering control to another
function in which can be done when the function making the call will only 
be returning what the function being called returns. 

See: http://en.wikipedia.org/wiki/Tail_call

=over 4

=item C<onload>

Creates the subclass for the FUN compiler, registers it, and sets up
the grammar, actions, and tailcall stage.

=cut

.namespace [ 'FUN::HLLCompiler' ]

.sub 'onload' :anon :load :init
    load_bytecode 'PCT.pbc'
    $P0 = get_hll_global 'Protomaker'
    $P1 = $P0.'new_subclass'('PCT::HLLCompiler', 'FUN::HLLCompiler')

    $P0 = new [ 'FUN::HLLCompiler' ]
    $P0.'language'('FUN')
    $P0.'parsegrammar'('FUN::Grammar')
    $P0.'parseactions'('FUN::Grammar::Actions')
    $P0.'addstage'('tailcall', 'after' => 'past')

    .return ()
.end

=item C<tailcall(past)>

Perform tailcall optimization on the given PAST tree.

TODO: this actually modifies the passed in tree.  It should probably 
not do that and instead create a new tree with the modifications

=cut

.sub 'tailcall' :method
    .param pmc past
    .param pmc adverbs         :slurpy :named

    .local pmc cache
    cache = self.'tailcall_subs'(past)

    .return (past)
.end

=item C<scan_children(past)>

Scan through the children of the given PAST root.

Returns the collected caches from the tailcall_subs() for the
children.

=cut

.sub 'scan_children' :method 
    .param pmc node

    .local pmc cache
    .local pmc child_analysis
    .local pmc children
    children = node.'iterator'()
    cache = new 'ResizablePMCArray'

  child_loop:
    unless children goto finish
    $P0 = shift children
    child_analysis = self.'tailcall_subs'($P0)
    cache.'append'(child_analysis)
    goto child_loop

  finish:
    .return (cache)
.end

=item C<tailcall_subs(past)>

Default tailcall opt.  Just scan the children.

=cut

.sub 'tailcall_subs' :method :multi(_,_)
    .param pmc node

    .return self.'scan_children'(node)
.end

=item C<tailcall_subs(PAST::Op past)>

Perform a post-order traversal of the PAST looking
for candidates of tailcall optimization.  Candidate
nodes from the analysis are returned as elements of
a ResizablePMCArray

=cut

.sub 'tailcall_subs' :method :multi(_,['PAST::Op'])
    .param pmc node

    .local pmc cache
    .local pmc children
    .local int clear
    clear = 0

    $S0 = node.'pasttype'()
    if $S0 == 'call' goto handle_call
    if $S0 == 'if' goto handle_if
    if $S0 == 'bind' goto full_scan

    # Other kinds of ops mean that something is being done and all
    # child analysis will be useless.  So mark them to be thrown away
    clear = 1
    goto full_scan

  handle_call:
    cache = self.'scan_children'(node)

    # only the last call in the tree (so the last
    # in evaluation) can be a tailcall.
    cache = new 'ResizablePMCArray'
    push cache, node
    
    goto finish

  handle_if:
    # analyse the three parts of the if.  We can ignore anything
    # from the first part (the test) since there is more to do after it.
    # Then combine the analyses two expressions of the primary and alternate
    # as the analysis of the if
    $P0 = node[0]
    self.'tailcall_subs'($P0)
    
    .local pmc left_context
    .local pmc right_context

    $P0 = node[1]
    left_context = self.'tailcall_subs'($P0)

    $P0 = node[2]
    right_context = self.'tailcall_subs'($P0)

    left_context.'append'(right_context)
    cache = left_context

    goto finish 

  full_scan:
    cache = self.'scan_children'(node)

  unless clear goto finish
    cache = new 'ResizablePMCArray'
    
  finish:

    .return (cache)
.end

=item C<tailcall_subs(PAST::Block past)>

Scan a block for tailcall optimizations.  If there are
candidate returns found then convert them to tailcalls.

=cut

.sub 'tailcall_subs' :method :multi(_,['PAST::Block'])
    .param pmc node

    .local pmc returns
    .local pmc children
    children = node.'iterator'()

  child_loop:
    unless children goto stop
    
    # A block starts a new scope for tailcalls
    # and processes each child in turn.  Works for this
    # language because a function (or block) is a single 
    # expression.
    $P0 = shift children
    returns = self.'tailcall_subs'($P0)

    self.'convert_to_tailcall'(returns)

    goto child_loop

  stop:

    $P0 = new 'ResizablePMCArray'
    .return ($P0)
.end

=item C<convert_to_tailcall(returns)>

Change the given array of (expected to be) 'call' 
PAST::Ops to 'inline's that perform tailcalls.

=cut

.sub 'convert_to_tailcall' :method
    .param pmc returns

  loop:
    unless returns goto loop_end
    $P0 = shift returns
    $P0.'pasttype'('inline')
    
    # the tailcall needs to set %r only because
    # the POST transform seems to expect a result
    # from every node but the last in a block
    $P0.'inline'(".return %0(%1)\n%r=1")
    goto loop
  loop_end:

    .return ()
.end

.include 'src/builtins.pir'

.include 'src/gen_grammar.pir'

.include 'src/gen_grammar-actions.pir'

# Local Variables:
#   mode: pir
#   fill-column: 100
# End:
# vim: expandtab shiftwidth=4:
